package List.Joseph;

/*
    解决约瑟夫问题
 */
public class Joseph {

    public static void main(String[] args) {
        //创建循环链表，包含41个节点
        Node<Integer> first = null;
        Node<Integer> pre = null;
        for (int i = 1; i <= 41; i++) {
            //第一个节点和最后一个节点要特殊处理
            if (i == 1) {
                first = new Node<>(i, null);
                pre = first;
            } else if (i == 41) {
                Node<Integer> n = new Node<>(i, null);
                n.next = first;
                pre.next = n;
            } else {
                Node<Integer> n = new Node<>(i, null);
                pre.next = n;
                pre = n;
            }
        }
        //利用count模拟报数
        int count = 1;
        //开始淘汰
        Node<Integer> current = first;
        while (current.next != current) {
            count++;
            current = current.next;
            if (count == 2) {
                System.out.print(current.next.item+" ");
                current.next = current.next.next;
                count = 0;
            }
        }
        //打印最后一个元素
        System.out.println();
        System.out.println(current.item);
    }

    private static class Node<T> {
        T item;
        Node<T> next;

        public Node(T item, Node<T> next) {
            this.item = item;
            this.next = next;
        }
    }
}
